<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>
<body>
    <script>
    //定义一个队列
    function Queue(){
        var items = [];   // 存储数据

        // 向队列尾部添加一个元素
        this.enqueue = function(item){
            items.push(item);
        };

        // 移除队列头部的元素
        this.dequeue = function(){
            return items.shift();
        };

        // 返回队列头部的元素
        this.head = function(){
            return items[0];
        };

        // 返回队列尾部的元素
        this.tail = function(){
            return items[items.length-1];
        };

        // 返回队列大小
        this.size = function(){
            return items.length;
        };

        // clear
        this.clear = function(){
            items = [];
        };

        // isEmpty 判断是否为空队列
        this.isEmpty = function(){
            return items.length == 0;
        };
    };


    //约瑟夫环
    function del_ring(arr_list){
        var queue=new Queue();
        //将数组插入队列之中
        for(var i=0;i<arr_list.length;i++){
            queue.enqueue(arr_list[i]);
        };
        //定义一个参数 用来判断是否需要从队列顶部弹出
        var index = 0;
        //队列长度不为1一直循环
        while(queue.size() != 1){
            //弹出一个元素判断是否需要删除
            var item=queue.dequeue();
            //并且参数++
            index++;
            //判断与3取余不等于0，塞入队列尾部
            if(index%3 != 0){
                queue.enqueue(item);
            }
        }
        //返回队列剩余元素
        return queue.tail();
    }

    //造数据
    var arr_list=[];
    for(var i=0;i<100;i++){
        arr_list.push(i);
    }

    console.log(del_ring(arr_list)); //90

    //斐波那契数列
    function feibonaqie(n){
        if(n<0){
            return false
        }
        if(n<3){
            return 1
        }
        var queue = new Queue();
        var index = 0;
        
        //将两个1存入队列之中
        queue.enqueue(1);
        queue.enqueue(1);
        //思路：队列中一直保存两个数 
        while(index<n-2){
            var dequeue=queue.dequeue();
            var head=queue.head();
            var next=dequeue+head;
            queue.enqueue(next);

            index++
        }
        //反回队列尾部数字
        return queue.tail();
    }

    console.log(feibonaqie(5))

    //for加队列实现杨辉三角 n表示行数
    function yanghui(n){
        var queue =new Queue();
        queue.enqueue(1);
        //控制层数
        for(var i=1;i<=n;i++){
            var line="";
            var pre=0;
            // 第二层for循环控制打印第 i 层
            for(var j=1; j<=i;j++){
                var item=queue.dequeue();
                line+=item+"";
                // 计算下一行的内容
                var value=item+pre;
                pre=item;
                //存入的是下一行的数
                queue.enqueue(value);
            }
            //每一层最后一个数字是1,上面的for循环没有计算最后一个数
            queue.enqueue(1);
            console.log(line);
        }
    }
    yanghui(5);
    </script>
</body>
</html>